// 给定一个整数数组nums和一个整数k，找出nums中和至少为k的最短非空子数组，并返回该子数组的长度，如果不存在这样的子数组，返回-1

// 思路，单调队列，计算数组前缀和，构造单调递增栈，这样计算当前前缀和和单调栈最小值的差，如果大于等于k则更新结果
// 时间复杂度：O(n)
// 空间复杂度：O(n)

function shortestSubarray(arr, k) {
    const sum = [0]
    for (let i = 0; i < arr.length; i++) {
        sum[i + 1] = sum[i] + arr[i]       
    }
    const queue = [0] // 存放索引，单调递增队列
    let ans = Infinity
    for (let i = 0; i < sum.length; i++) {
        while (queue.length && sum[i] - sum[queue[0]] >= k) {
            let len = i - queue.shift()
            ans = Math.min(ans, len)
        }
        while (queue.length && sum[queue[queue.length - 1]] > sum[i]) {
            queue.pop()
        }
        queue.push(i)
    }
    return ans === Infinity ? -1 : ans
}

let nums = [2, -1, 2], k = 3
console.log(shortestSubarray(nums, k));